package top.jolyoulu.力扣._1048_最长字符串链;

//给出一个单词数组 words ，其中每个单词都由小写英文字母组成。
//
// 如果我们可以 不改变其他字符的顺序 ，在 wordA 的任何地方添加 恰好一个 字母使其变成 wordB ，那么我们认为 wordA 是 wordB 的
//前身 。
//
//
// 例如，"abc" 是 "abac" 的 前身 ，而 "cba" 不是 "bcad" 的 前身
//
//
// 词链是单词 [word_1, word_2, ..., word_k] 组成的序列，k >= 1，其中 word1 是 word2 的前身，word2 是
// word3 的前身，依此类推。一个单词通常是 k == 1 的 单词链 。
//
// 从给定单词列表 words 中选择单词组成词链，返回 词链的 最长可能长度 。
//
// 示例 1：
//
//
//输入：words = ["a","b","ba","bca","bda","bdca"]
//输出：4
//解释：最长单词链之一为 ["a","ba","bda","bdca"]
//
//
// 示例 2:
//
//
//输入：words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
//输出：5
//解释：所有的单词都可以放入单词链 ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"].
//
//
// 示例 3:
//
//
//输入：words = ["abcd","dbqca"]
//输出：1
//解释：字链["abcd"]是最长的字链之一。
//["abcd"，"dbqca"]不是一个有效的单词链，因为字母的顺序被改变了。
//
//
//
//
// 提示：
//
//
// 1 <= words.length <= 1000
// 1 <= words[i].length <= 16
// words[i] 仅由小写英文字母组成。
//
//
// Related Topics 数组 哈希表 双指针 字符串 动态规划 👍 237 👎 0

import top.jolyoulu.utils.TimerUtils;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Answer1 {

    /*
        思路：
            什么是前身：如果我们可以 不改变其他字符的顺序 ，在 wordA 的任何地方添加 恰好一个 字母使其变成 wordB ，那么我们认为 wordA 是 wordB 的前身
            1.根据前身的定义，那么先吧words 按照字母长度从小打到排序，方便后续使用
            2.定义一个记录record用于保存当前字符的前身字符数
            3.遍历所有words，获取每一个word在words数组中查找他的前身字符，当找到就返回字符所在的下标
            4.让record[当前的字符长度] += record[前身字符长度]，这样即可得出整个前身字符的长度

    */
    public int longestStrChain(String[] words) {
        Arrays.sort(words,(a,b) -> a.length() - b.length());
        int[] record = new int[words.length];
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < words.length; i++) {
            record[i] = 1;
            //找w1的前身
            int pre = getPredecessorIndex(words, i, record);
            if (i != pre && (!words[i].equals(words[pre]))) {
                record[i] += record[pre];
            }
            if (record[i] > max){
                max = record[i];
            }
//            System.out.println(words[i] + "的前身是"+words[pre]+"（"+record[pre]+"）");
        }
        return max;
    }

    public int getPredecessorIndex(String[] words, int index, int[] record) {
        int max = -1;
        for (int i = 0; i < words.length; i++) {
            if (isPredecessor(words[i], words[index])) {
                if (max == -1) {
                    max = i;
                } else if (record[i] > record[max]) {
                    max = i;

                }
            }
        }
        return max;
    }

    public boolean isPredecessor(String word1, String word2) {
        if (word1.equals(word2)) {
            return true;
        }
        if (word1.length() != word2.length() - 1) {
            return false;
        }
        int w1I = 0;
        int w2I = 0;
        for (int i = 0; i < word2.length(); i++) {
            if (w2I - w1I > 1){
                return false;
            }
            if (w1I == word1.length()) {
                return true;
            }
            char c1 = word1.charAt(w1I);
            char c2 = word2.charAt(w2I);
            if (c1 == c2) {
                w1I++;
            }
            w2I++;
        }
        return w1I == word1.length();
    }

    public static void main(String[] args) {
        Answer1 answer1 = new Answer1();
        System.out.println("用例1=======================================");
        new TimerUtils<String[],Integer>().timer(
                () -> {
                    String[] arg = new String[]{"a","b","ba","bca","bda","bdca"};
                    System.out.println("words = "+ Arrays.toString(arg));
                    return arg;
                },
                answer1::longestStrChain,
                (res) -> {
                    System.out.println("结果："+res);
                }
        );
        System.out.println("用例2=======================================");
        new TimerUtils<String[],Integer>().timer(
                () -> {
                    String[] arg = new String[]{"xbc","pcxbcf","xb","cxbc","pcxbc"};
                    System.out.println("words = "+ Arrays.toString(arg));
                    return arg;
                },
                answer1::longestStrChain,
                (res) -> {
                    System.out.println("结果："+res);
                }
        );
        System.out.println("用例3=======================================");
        new TimerUtils<String[],Integer>().timer(
                () -> {
                    String[] arg = new String[]{"abcd","dbqca"};
                    System.out.println("words = "+ Arrays.toString(arg));
                    return arg;
                },
                answer1::longestStrChain,
                (res) -> {
                    System.out.println("结果："+res);
                }
        );
        System.out.println("用例4=======================================");
        new TimerUtils<String[],Integer>().timer(
                () -> {
                    String[] arg = new String[]{"a","b","ab","bac"};
                    System.out.println("words = "+ Arrays.toString(arg));
                    return arg;
                },
                answer1::longestStrChain,
                (res) -> {
                    System.out.println("结果："+res);
                }
        );
        System.out.println("用例5=======================================");
        new TimerUtils<String[],Integer>().timer(
                () -> {
                    String[] arg = new String[]{"a","ab","ac","bd","abc","abd","abdd"};
                    System.out.println("words = "+ Arrays.toString(arg));
                    return arg;
                },
                answer1::longestStrChain,
                (res) -> {
                    System.out.println("结果："+res);
                }
        );
        System.out.println("用例6=======================================");
        new TimerUtils<String[],Integer>().timer(
                () -> {
                    String[] arg = new String[]{"bdca", "bda", "ca", "dca", "a"};
                    System.out.println("words = " + Arrays.toString(arg));
                    return arg;
                },
                answer1::longestStrChain,
                (res) -> {
                    System.out.println("结果：" + res);
                }
        );
        System.out.println("用例7=======================================");
        new TimerUtils<String[],Integer>().timer(
                () -> {
                    String[] arg = new String[]{"wnyxmflkf","xefx","usqhb","ttmdvv","hagmmn","tmvv","pttmdvv","nmzlhlpr","ymfk","uhpaglmmnn","zckgh","hgmmn","isqxrk","isqrk","nmzlhpr","uysyqhxb","haglmmn","xfx","mm","wymfkf","tmdvv","uhaglmmn","mf","uhaglmmnn","mfk","wnymfkf","powttkmdvv","kwnyxmflkf","xx","rnqbhxsj","uysqhb","pttkmdvv","hmmn","iq","m","ymfkf","zckgdh","zckh","hmm","xuefx","mv","iqrk","tmv","iqk","wnyxmfkf","uysyqhb","v","m","pwttkmdvv","rnqbhsj"};
                    System.out.println("words = " + Arrays.toString(arg));
                    return arg;
                },
                answer1::longestStrChain,
                (res) -> {
                    System.out.println("结果：" + res);
                }
        );
    }
}
